package com.jorenwu.asymmetric;

import java.math.BigInteger;
import java.util.Random;

public class BaseCalculator
{
	public static final BigInteger TWO = new BigInteger("2");
/*
 * retrun jacobi(a/n)
 */
	public BigInteger Jacobi(BigInteger a, BigInteger N)
	{
		if (a.equals(BigInteger.ONE))
			return BigInteger.ONE;
		else if (a.mod(BaseCalculator.TWO).equals(BigInteger.ZERO))
		{
			BigInteger temp = ((N.pow(2)).subtract(BigInteger.ONE))
					.divide(new BigInteger(String.valueOf(8)));
			if (temp.mod(BaseCalculator.TWO).equals(BigInteger.ZERO))
				return Jacobi(a.divide(BaseCalculator.TWO), N);
			else
				return Jacobi(a.divide(BaseCalculator.TWO), N).negate();
		} else if (((a.subtract(BigInteger.ONE)).multiply(N
				.subtract(BigInteger.ONE))).divide(
				new BigInteger(String.valueOf(4))).mod(BaseCalculator.TWO)
				.equals(BigInteger.ZERO))
			return Jacobi(N.mod(a), a);
		else
			return Jacobi(N.mod(a), a).negate();
	}
/*
 * get a big radom number
 */
	public BigInteger getBigRandomInt(int nbits)
	{
		BigInteger result = null;
		boolean isGenerated = true;
		while (isGenerated)
		{
			try
			{
				Random rand = new Random(System.currentTimeMillis());
				result = new BigInteger(nbits, rand);
				result = result.abs();
				result = result.or(BigInteger.ONE);
				result = result.or((BigInteger.ONE).shiftLeft(nbits - 1));
				isGenerated = false;
			} catch (Exception ex)
			{
				isGenerated = true;
			}
		}
		return result;
	}

	/*
	 * return n!
	 */
	public BigInteger factoria(BigInteger n)
	{
		if (n.equals(BigInteger.ONE))
			return BigInteger.ONE;
		else
			return n.multiply(factoria(n.subtract(BigInteger.ONE)));
	}
	
	/*
	 * return b,which b*b=a, here i use the Newton interator algorism: b=(b+a/b)/2
	 */
	public BigInteger sqrt(BigInteger N)
	{
		BigInteger result=N.divide(BaseCalculator.TWO);
		while(result.multiply(result).subtract(N).compareTo(BigInteger.ONE.divide(new BigInteger("100000000")))>0)
			result=result.add(N.divide(result)).divide(BaseCalculator.TWO);
		return result;
	}

	public BigInteger Pollard(BigInteger N)
	{
		BigInteger factor = null;
		// here you can modify the number bigger to factorize your bigger bigger
		// number
		BigInteger B = new BigInteger("100");
		//BigInteger B = sqrt(N);
		BigInteger k = factoria(B);
		// generate the random number a
		while (true)
		{
			Random rand = new Random(System.currentTimeMillis());
			BigInteger a = new BigInteger(512, rand);
			a = (a.mod(N)).subtract(BigInteger.ONE);
			if (a.compareTo(BigInteger.ZERO) == 0)
				a.add(BaseCalculator.TWO);
			if (a.compareTo(BigInteger.ONE) == 0)
				a.add(BigInteger.ONE);
			factor = a.modPow(k, N);
			factor = factor.subtract(BigInteger.ONE).mod(N).gcd(N);
			if (factor.compareTo(BigInteger.ONE) > 0 && factor.compareTo(N) < 0)
				break;
			else
				continue;
		}
		return factor;
	}
}
